using System;
using System.Collections.Generic;

namespace Test.ConsoleProgram.Algorithm.Solution
{
    [TestDescription("算法: 0043. 字符串相乘")]
    public class No0043_Multiply : AbsBaseTestItem
    {
        /*
        给定两个以字符串形式表示的非负整数 num1 和 num2，返回 num1 和 num2 的乘积，它们的乘积也表示为字符串形式。
        说明：
            1. num1 和 num2 的长度小于110。
            2. num1 和 num2 只包含数字 0-9。
            3. num1 和 num2 均不以零开头，除非是数字 0 本身。
            4. 不能使用任何标准库的大数类型（比如 BigInteger）或直接将输入转换为整数来处理。
        */

        public override void OnTest()
        {
            Assert.TestExe(Multiply, "2", "3", "6");
            Assert.TestExe(Multiply, "123", "456", "56088");
        }

        public string Multiply(string num1, string num2)
        {
            // 算法: 0415. 字符串相加
            string AddStrings(string num1, string num2)
            {
                var ans = new List<int>();
                int i = num1.Length - 1, j = num2.Length - 1, add = 0;
                while (i >= 0 || j >= 0 || add != 0)
                {
                    int x = i >= 0 ? num1[i] - '0' : 0;
                    int y = j >= 0 ? num2[j] - '0' : 0;
                    int result = x + y + add;
                    ans.Add(result % 10);
                    add = result / 10;
                    i--;
                    j--;
                }
                ans.Reverse();
                return string.Join("", ans);
            }

            if (num1 == "0" || num2 == "0") return "0";
            string ans = "0";
            int m = num1.Length, n = num2.Length;
            for (int i = n - 1; i >= 0; i--)
            {
                var curr = new List<int>();
                int add = 0;
                for (int j = n - 1; j > i; j--)
                {
                    curr.Add(0);
                }
                int y = num2[i] - '0';
                for (int j = m - 1; j >= 0; j--)
                {
                    int x = num1[j] - '0';
                    int product = x * y + add;
                    curr.Add(product % 10);
                    add = product / 10;
                }
                if (add != 0)
                {
                    curr.Add(add % 10);
                }
                curr.Reverse();
                ans = AddStrings(ans, string.Join("", curr));
            }
            return ans;
        }
    }
}
